import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class Solution1 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int sum = 0;
        for(int i = 0; i<n-1; i++) {
            //买入
            if(prices[i+1] > prices[i]) {
                int begin = prices[i];
                int j = i+1;
                while (i<n-1 && prices[j] > prices[j-1]) {
                    j++;
                }
                sum += prices[j-1] - begin;
                i = j-1;
            }
        }
        return sum;
    }
}

class Solution2 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = -prices[0];
        for(int i = 1; i<n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
        }
        return dp[n-1][1];
    }
}
class Solution3 {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int sum = 0;
        int begin = -1;
        for(int i = 0; i<n; i++) {
            if(i+1 < n && prices[i+1] >= prices[i] && begin == -1) {
                begin = prices[i];
            }else if(i == n-1 || prices[i+1] < prices[i] && begin != -1){
                sum += prices[i] - begin;
                begin = -1;
            }
        }
        return sum;
    }
}

class Solution4 {
    public int maxProfit(int[] prices) {
        int  n = prices.length;
        int sum = 0;
        for(int i = 0; i<n-1; i++) {
            if(prices[i+1] > prices[i]) {
                sum += prices[i+1] - prices[i];
            }
        }
        return sum;
    }
}

class Solution5 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        int n = nums.length;
        int sum = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int x:nums) {
            queue.add(x);
        }
        for(int i = 0; i<k; i++) {
            int x = queue.poll();
            queue.add(-x);
        }
        while (!queue.isEmpty()) {
            sum += queue.poll();
        }
        return sum;
    }
}

class Student {
    public String name;
    public int height;
}
class Solution6 {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Student[] students = new Student[n];
        for(int i = 0; i<n; i++) {
            students[i] = new Student();
            students[i].name = names[i];
            students[i].height = heights[i];
        }

        Arrays.sort(students,(a,b)->a.height-b.height);
        String[] strs = new String[n];
        for(int i = 0; i<n; i++) {
            strs[i] = students[i].name;
        }
        return strs;
    }
}

class Solution {
    public String[] sortPeople(String[] names, int[] heights) {
        int n = names.length;
        Integer[] index = new Integer[n];
        for(int i = 0; i<n; i++) {
            index[i] = i;
        }
        Arrays.sort(index, (i,j)->
        {
            return heights[j] - heights[i];
        });

        String[] ret = new String[n];
        for(int i = 0; i<n; i++) {
            ret[i] = names[index[i]];
        }
        return ret;
    }
}

public class Test1 {
    public static void main(String[] args) {
        String[] strs = {"fs","fdsafd","ewr"};
        int[] h = {2,3,1};
        String[] ret = new Solution().sortPeople(strs,h);
    }
    public static void main2(String[] args) {
        int[] nums = {4,2,3};
        int ret = new Solution5().largestSumAfterKNegations(nums,1);
    }
    public static void main1(String[] args) {
        int[] nums = {1,2,3,4,5};
        int ret = new Solution3().maxProfit(nums);
    }
}
